#include <iostream>
using namespace std;

template<class T>
class Node {
public:
    Node(T data) :data(data),left(nullptr),right(nullptr){
        
    }
    void set_left(Node<T> *left) {
        this->left = left;
    }
    void set_right(Node<T> *right) {
        this->right = right;
    }
    // 前序遍历
    void pre_order_traverse() {
        cout << data << " ";
        if (left != nullptr)
            left->pre_order_traverse();
        if (right != nullptr)
            right->pre_order_traverse();
    }
    // 中序遍历
    void infix_order_traverse() {
        if (left != nullptr)
            left->infix_order_traverse();
        cout << data << " ";
        if (right != nullptr)
            right->infix_order_traverse();
    }
    // 后序遍历
    void post_orider_traverse() {
        if (left != nullptr)
            left->post_order_traverse();
        if (right != nullptr)
            right->post_order_traverse();
        cout << data << " ";
    }
    // 前序查找
    Node<T> *pre_order_search(T data) {
        if (this->data == data) 
            return this;

        Node<T> *t = nullptr;
        if (left != nullptr)
            t = left->pre_order_search(data);
        if (t != nullptr)
            return t;

        if (right != nullptr)
            t = right->pre_order_search(data);
        return t;
    }
    // 中序查找
    Node *infix_order_search(T data) {
        Node<T> *t = nullptr;
        if (left != nullptr)
            t = left->infix_order_search(data);
        if (t != nullptr)
            return t;

        if (this->data == data) 
            return this;

        if (right != nullptr)
            t = right->infix_order_search(data);
        return t;
    }
    // 后序查找
    Node *post_order_search(T data) {
        Node<T> *t = nullptr;
        if (left != nullptr)
            t = left->post_order_search(data);
        if (t != nullptr)
            return t;

        if (right != nullptr)
            t = right->post_order_search(data);
        if (t != nullptr)
            return t;

        if (this->data == data) 
            return this;
        return nullptr;
    }
    // 删除结点
    void del_node(T data) {
        if (left != nullptr && left->data == data) {
            delete left;
            left = nullptr;
            return;
        }
        if (right != nullptr && right->data == data) {
            delete right;
            right = nullptr;
            return;
        }
        if (left != nullptr)
            left->del_node(data);
        if (right != nullptr) 
            right->del_node(data);
    }
private:   
    T data;
    Node<T> *left;
    Node<T> *right;
};